package com.lanou.list;

import java.util.ArrayList;
import java.util.Collection;

/**
 * 单向链表
 * @author zyj
 * @date 2022年05月18日 11:19
 */
public class SingleLinkedList<E> extends AbstractList<E> implements List<E>{

    private Node<E> head;

    public Node<E> getHead(){
        return head;
    }

    @Override
    public E get(int index) {
        Node<E> node = node(index);
        return node.item;
    }



    @Override
    public E set(int index, E element) {
        Node<E> node = node(index);
        E oldItem = node.item;
        node.item = element;
        return oldItem;
    }

    @Override
    public void add(int index, E element) {
        if (index == 0){
            head = new Node<E>(element,head);
        }else {
            Node<E> prev = node(index - 1);
            prev.next = new Node<E>(element, prev.next);
        }
        size++;
    }

    @Override
    public E remove(int index) {
        rangeCheck(index);
        E e = null;
        if (index == 0){
            e = head.item;
            head = head.next;
        }else {
            Node<E> prev = node(index - 1);
            Node<E> cur = prev.next;
            prev.next = prev.next.next;
            cur.next = null;
            e = cur.item;
        }
        size--;
        return e;
    }

    @Override
    public int indexOf(E element) {
        int index = 0;
        if (null == element){
            for (Node<E> x = head;x != null;x = x.next) {
                if (null == x.item){
                    return index;
                }
                index++;
            }
        }else {
            for (Node<E> x = head;x != null;x = x.next) {
                if (element.equals(x.item)){
                    return index;
                }
                index++;
            }
        }
        return -1;
    }

    @Override
    public void clear() {
        while (head != null){
            Node<E> next = head.next;
            head.item = null;
            head.next = null;
            head = next;
        }
    }

    private Node<E> node(int index) {
        Node<E> cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur;
    }

    private class Node<E>{
        E item;
        Node<E> next;

        public Node(E item,Node<E> next){
            this.item = item;
            this.next = next;
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("head→");
        for ( Node<E> x = head;x != null;x = x.next) {
            sb.append(x.item).append("→");
        }

        sb.append("null");
        return sb.toString();
    }


    public static void main(String[] args) {
        SingleLinkedList<Integer> list = new SingleLinkedList<>();

        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);

        list.add(0,6);
        list.add(7);
        System.out.println(list.set(0, 8));
        System.out.println(list.size());
        System.out.println(list.indexOf(3));

        list.remove(0);
        list.remove(5);
        list.remove(2);
        System.out.println(list);
    }

    private void rangeCheck(int index) {
        int size = size();
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }


}

